package tree;

/**
 * @author wujun
 * @date 17-11-27.
 * <p>
 * <p>
 * 求两个节点的最短公共节点， 可以使用后序遍历或者是并查集来完成
 */
public class Solution236 {

    public TreeNode c  (TreeNode root, TreeNode p, TreeNode q) {
        return lowestCommonAncestorUsingPostOrder(root, p, q);
//        return lowestCommonAncestorUsingUnionFindSet(root, p, q);
    }

    private TreeNode lowestCommonAncestorUsingPostOrder(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestorUsingPostOrder(root.left, p, q);
        TreeNode right = lowestCommonAncestorUsingPostOrder(root.right, p, q);

        if (left != null && right != null) {
            return root;
        }

        return left == null ? right : left;
    }

    private TreeNode lowestCommonAncestorUsingUnionFindSet(TreeNode root, TreeNode p, TreeNode q) {
        return null;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
